#include <iostream>

void counting_sort(int* arr, int* sorted_arr, int l)
{
    int max = arr[0];
    for(int i = 1; i < l; i++)
    {
        if(arr[i] > max)
        {
            max = arr[i];
        }
    }
    max++;
   
    int *count_arr = new int[max];

    for(int i = 0; i < max; i++)
    {
        count_arr[i] = 0;
    }

    for(int i = 0; i < l; i++)
    {
        count_arr[arr[i]]++;
    }
    
    for(int i = 1; i < max; i++)
    {
        count_arr[i] += count_arr[i - 1];
    }

    for(int i = l; i > 0; i--)
    {
        sorted_arr[count_arr[arr[i - 1]] - 1] = arr[i - 1];
        count_arr[arr[i - 1]]--;
    }

    delete count_arr;
}

void print_array(int *a, int n)
{
    for(int i = 0; i < n; i++)
    {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;
}

int main(int argc, char** argv)
{
    int array[10] = {3, 4, 6, 3, 8, 4, 14, 40, 9, 10};
    int size = sizeof(array)/sizeof(array[0]);
    int *sorted_arr = new int[size];
    
    print_array(array, size);
    counting_sort(array, sorted_arr, size);
    print_array(sorted_arr, size);

    delete sorted_arr;

    return 0;
}
